/**
 * 
 */
package de.gee.erep.shared.utils.sort;

import java.util.Comparator;
import java.util.List;

/**
 * @author Matthew Gee created: 03.04.2011
 * @param <T>
 */
public abstract class Heapsort<T extends Comparable<T>> implements Sorter<T> {

	/***/
	private static final long serialVersionUID = 1L;

	@Override
	public abstract T[] sort(T[] toSort);

	public abstract void sort(List<T> list, Comparator<? super T> c);

	public Heapsort() {
	}

	/**
	 * @param toSort
	 */
	protected void buildMaxHeap(T[] toSort) {
		for (int i = ((toSort.length - 1) / 2); i >= 0; i--) {
			sink(toSort, i, toSort.length - 1);
		}
	}

	protected void sink(T[] toSort, int i, int r) {
		int max = 0;
		if ((2 * i + 1) <= r && toSort[2 * i + 1].compareTo(toSort[i]) == 1) {
			max = 2 * i + 1;
		} else {
			max = i;
		}
		if (2 * i + 2 <= r && toSort[2 * i + 2].compareTo(toSort[max]) == 1) {
			max = 2 * i + 2;
		}
		if (max != i) {
			swap(toSort, i, max);
			sink(toSort, max, r);
		}
	}

	protected T[] swap(T[] src, int i, int j) {
		T tmp = src[i];
		src[i] = src[j];
		src[j] = tmp;
		return src;
	}

	/**
	 * @param toSort
	 */
	@SuppressWarnings("rawtypes")
	protected void buildMaxHeap(Object[] toSort, Comparator c) {
		for (int i = ((toSort.length - 1) / 2); i >= 0; i--) {
			sink(toSort, i, toSort.length - 1, (Comparator) c);
		}
	}

	/**
	 * @param toSort
	 * @param i
	 * @param r
	 * @param c
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	protected void sink(Object[] toSort, int i, int r, Comparator c) {
		int max = 0;
		if ((2 * i + 1) <= r && c.compare(toSort[2 * i + 1], toSort[i]) == 1) {
			max = 2 * i + 1;
		} else {
			max = i;
		}
		if (2 * i + 2 <= r && c.compare(toSort[2 * i + 2], toSort[max]) == 1) {
			max = 2 * i + 2;
		}
		if (max != i) {
			swap(toSort, i, max);
			sink(toSort, max, r, c);
		}
	}

	/**
	 * Swaps x[a] with x[b].
	 */
	protected static void swap(Object[] x, int a, int b) {
		Object t = x[a];
		x[a] = x[b];
		x[b] = t;
	}
}
